package demo1;

import java.util.Stack;

public class Sort {
    public void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private void quick(int[] array, int begin, int end) {
        if(begin >= end) {
            return;
        }
        int left = begin;
        int right = end;
        int pivot = parttion(array,left,right);
        quick(array,begin,pivot-1);
        quick(array,pivot+1,end);
    }

    /**
     * hoare法
     * @param array
     * @param left
     * @param right
     * @return
     */
    private int parttion(int[] array, int left, int right) {
        int start = left;
        int tmp = array[left];
        while (left < right) {
            while (array[right] >= tmp && left < right) {
                right--;
            }
            //todo:先检查前面的会不会有问题
            while (array[left] <= tmp && left < right) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,start,right);
        return right;
    }

    /**
     * 挖坑法
     * @param array
     * @param left
     * @param right
     * @return
     */
    private int parttion1(int[] array, int left, int right) {
        int start = left;
        int tmp = array[left];
        while (left < right) {
            while (array[right] >= tmp && left < right) {
                right--;
            }
            array[left] = array[right];
            while (array[left] <= tmp && left < right) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    private void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    //非递归实现快排
    public void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = array.length - 1;
        int pivot = parttion(array,start,end);
        if(pivot-1 > start) {
            stack.push(start);
            stack.push(pivot-1);
        }
        if(pivot+1 < end) {
            stack.push(pivot + 1);
            stack.push(end);
        }
        while(!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            //使pivot更趋近于中间数
             //少于多少时选择直接插入排序
            pivot = parttion(array,start,end);
            if(pivot-1 > start) {
                stack.push(start);
                stack.push(pivot-1);
            }
            if(pivot+1 < end) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }

    //合并排序
    public void MergeSort(int[] array) {

    }

    private void MergeSortFunc(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        MergeSortFunc(array, left, mid);
        MergeSortFunc(array, mid + 1, right);

        merge(array, left, mid, right);
    }

    private void merge(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int[] temp = new int[right - left + 1];
        int k = 0;
        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] < array[s2]) {
                temp[k++] = array[s1++];
            } else {
                temp[k++] = array[s2++];
            }
        }
        while(s1 <= e1) {
            temp[k++] = array[s1++];
        }
        while(s2 <= e2) {
            temp[k++] = array[s2++];
        }
        for(int i = 0; i <= k; i++) {
            array[i+left] = temp[i];
        }
    }
}
